1. Field of the Invention
The present invention relates to encoding methods and encoders for information bits used in, for example, recording and transmission.
2. Description of the Related Art
A linear code C of degree k having a code length n can be encoded by the product of a generator matrix G and information bits c. When the linear code C is a systematic code, parity bits can be generated by the product of a parity generator matrix P and the information bits c. Generally, the size of the parity generator matrix P is (n−k)×k. If the code rate r=k/n is constant, the parity generator matrix P increases in size in proportion to the square of the code length n.
When the linear code C is a cyclic code, the systematic code can be easily encoded by polynomial operations. In other words, for example, the product of a polynomial M(x) having information bits as coefficients and xn−k is divided by a generator polynomial G(x), and the remainder is obtained. As a result, parity bits can be computed. An encoder can be implemented by using a feedback shift register. It is unnecessary to prepare a parity generator matrix.
In the linear code C, if a codeword resulting from cyclically shifting an arbitrary codeword by p bit positions is also a codeword of the linear code C, the linear code C is referred to as a quasi-cyclic (QC) code. Since a QC code when p=1 is a cyclic code, the QC code can be encoded by a generator polynomial. In contrast, generally a QC code when p≠1 cannot be treated as a normal cyclic code. Thus, the QC code is required to be encoded by the generator matrix G or the parity generator matrix P. The longer the code length is, the larger the generator matrix becomes. As a result, the encoder requires a high-capacity ROM.
For the encoding of cyclic codes using polynomial operations, please refer to “Error Control Coding: Fundamentals and Applications” by Shu Lin and Daniel J. Costello, Jr. (Prentice-Hall, 1983).